package slidingwindowmaximum

/*
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。
*/
func maxSlidingWindow(nums []int, k int) []int {
	q := Constructor() 
	n := len(nums)
	res := make([]int,0)
	// 前K入队
	for i:=0;i<k;i++{
		q.push(nums[i])
	}
	// 开始记录
	// 前k个最大值
	res = append(res, q.front())
	for i:=k;i<n;i++ {
		// 滑动窗口
		// 先移除
		q.pop(nums[i-k])  // 当然，队列里可能没有保存-不操作即可
		// 压入新元素
		q.push(nums[i])
		// 记录当前最大值
		res = append(res, q.front())
	}
	return res
}

// 单调队列
// 随着窗口移动 进出数据，并得到最大值
// 保证队列中的元素单调递减 那么队头就是窗口里的最大值
type MyQueue struct {
	q []int
}
func Constructor() MyQueue{
	return MyQueue{}
}
func (this *MyQueue) pop(val int) {
	// pop需要判空
	// 弹出时，需要比较要弹出的元素是否等于队头元素，相等则弹出
	if len(this.q) !=0 && val == this.front(){
		this.q = this.q[1:] //出队 
	}
}
// push
func (this *MyQueue) push(x int) {
	// 如果元素大于入口，则后端元素弹出  保证单调性
	for len(this.q)!=0 && x > this.q[len(this.q)-1]{
		this.q = this.q[:len(this.q)-1]  // 弹出队尾元素
	}
	//push
	this.q = append(this.q, x)
}
//获得队头元素
func (this *MyQueue) front() int {
	return this.q[0]
}
